//最长连续递增子序列
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) 
    {
        //dp[i] 以nums[i]为结束时 最长的连续递增序列
        vector<int>dp(nums.size(),1);
        int res=1;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i-1]<nums[i])
            {
                dp[i]=dp[i-1]+1;
                res=res>dp[i]?res:dp[i];
            }
        }
        return res;
    }
};

//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        if(nums.empty()) return 0;
        int res=1;
        //dp[i] 以nums[i]结尾的最长递增子序列的长度
        vector<int>dp(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                    res=dp[i]>res?dp[i]:res;
                }
            }
        }
        return res;
    }
};
//最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        //dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B
        //最长重复子数组长度为dp[i][j]
        int res=0;
        int m=nums1.size()+1;
        int n=nums2.size()+1;
        vector<vector<int>>dp(m,vector<int>(n,0));
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(nums1[i-1]==nums2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    res=res>dp[i][j]?res:dp[i][j];
                }
            }
        } 
        return res;
    }
};
//最长公共子序列
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        //dp[i][j] text1的前i个字符 text2的前j个字符的最长公共自序列
        //dp[i][j]=dp[i-1][j-1]+1 
        //dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        int m=text1.size(),n=text2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        //dp[0][j]等于0  dp[i][0]等于0
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};
